//给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。 
//
// 对于每个单元格，你可以往上，下，左，右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
//输出：4 
//解释：最长递增路径为 [1, 2, 6, 9]。 
//
// 示例 2： 
//
// 
//
// 
//输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
//输出：4 
//解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
// 
//
// 示例 3： 
//
// 
//输入：matrix = [[1]]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 200 
// 0 <= matrix[i][j] <= 2³¹ - 1 
// 
//
// 
//
// 
// 注意：本题与主站 329 题相同： https://leetcode-cn.com/problems/longest-increasing-path-
//in-a-matrix/ 
//
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 记忆化搜索 数组 动态规划 矩阵 👍 31 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)
class SolutionOffer2_112 {

    int m, n;
    int[][] dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    public int longestIncreasingPath(int[][] matrix) {
        m = matrix.length;
        n = matrix[0].length;
        int[][] memo = new int[m][n];
        int ans = 0;
        for(int i = 0; i < m; i++){
            for (int j = 0; j < n; j++) {
                ans = Math.max(dfs(i, j, matrix, memo), ans);
            }
        }
        return ans;
    }

    private int dfs(int i, int j, int[][] matrix, int[][] memo) {
        if(memo[i][j] != 0){
            return memo[i][j];
        }
        // 必须加1，否则会死递归
        memo[i][j]++;
        for(int k = 0; k < 4; k++){
            int nextI = i + dirs[k][0];
            int nextJ = j + dirs[k][1];
            if( nextI>=0&&nextI<m&&nextJ>=0&&nextJ<n&&matrix[nextI][nextJ] > matrix[i][j]) {
                memo[i][j] = Math.max(memo[i][j], 1 + dfs(nextI, nextJ, matrix, memo));
            }
        }
        return memo[i][j];
    }

    public static void main(String[] args) {
        int i = new SolutionOffer2_112().longestIncreasingPath(new int[][]{{9, 9, 4}, {6, 6, 8}, {2, 1, 1}});
        System.out.println(i);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
